#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	if (*pphead == NULL)
		return;
	else
	{
		SLTNode* cur = *pphead;
		while (cur)
		{
			SLTNode* next = cur->next;
			free(cur);
			cur = next;
		}
	}
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = BuySLTNode(x);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = BuySLTNode(x);
	}
}
void ReverseSList(SLTNode** head)
{
	assert(*head);
	SLTNode* cur = *head;
	SLTNode* prev = NULL;
	while (cur)
	{
		SLTNode* next = cur->next;

		cur->next = prev;
		prev = cur;

		cur = next;
	}
	*head = prev;
}
SLTNode* MergeSList(SLTNode* A, SLTNode* B)
{
	assert(A);
	assert(B);

	SLTNode* curA = A;
	SLTNode* curB = B;
	SLTNode* newhead = (SLTNode*)malloc(sizeof(SLTNode*));
	SLTNode* newcur = newhead;
	
	while (curA && curB)
	{
		if (curA->data >= curB->data)
		{
			newcur->next = curA;
			curA = curA->next;
		}
		else
		{
			newcur->next = curB;
			curB = curB->next;
		}
		
		newcur = newcur->next;
	}
	if (curA)
	{
		newcur->next = curA;
	}
	if (curB)
	{
		newcur->next = curB;
	}

	return newhead->next;
}
void Test()
{
	SLTNode* head = NULL;
	SListPushBack(&head, 1);
	SListPushBack(&head, 2);
	SListPushBack(&head, 3);
	SListPushBack(&head, 4);
	SLTNode* newhead = NULL;
	SListPushBack(&newhead, 1);
	SListPushBack(&newhead, 2);
	SListPushBack(&newhead, 3);
	SListPushBack(&newhead, 4);
	ReverseSList(&head);
	ReverseSList(&newhead);
	SListPrint(head);
	SListPrint(newhead);
	SListPrint(MergeSList(head, newhead));
}

int main()
{
	Test();
	return 0;
}